﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ArrangeNegativePositiveInOrder
{
    class Program
    {
        static void Main(string[] args)
        {
            //int[] input = { 1, 7, -5, 9, -12, 15 };
            int[] input = { 5, -1, 3, -2, 0, 3, -7, 4, -6 };
            int[] result = OrderByOrderApperance(input);

            Display(result);

            Console.Read();
        }

        public static int[] OrderByOrderApperance(int[] input)
        {
            int p = 0;
            int q = 0;

            int i = 0;

            int count = 0;
            while (i < input.Length)
            {
                if (input[i] < 0)
                {
                    if (q <= i)
                    {
                        Swap(input, i, p);

                        if (p == q)
                            q++;

                        if (p > 1)
                        {
                            i = p--;
                        }

                        //Display(input);                   
                    }
                    else
                    {
                        i = q;
                        p = 0;
                    }
                }
                else
                {
                    if (p > 0)
                        p++;
                    else
                        p = i;

                    i++;
                }

                count++;
            }

            return input;
        }

        private static int[] Swap(int[] input, int a, int b)
        {
            if (a != b)
            {
                input[a] ^= input[b];
                input[b] ^= input[a];
                input[a] ^= input[b];
            }

            return input;
        }

        private static void Display(int[] input)
        {
            for (int i = 0; i < input.Length; i++)
            {
                Console.Write(" {0} ", input[i]);
            }
            Console.WriteLine();
        }
    }
}
